The present disclosure relates to a cache oblivious algorithm for generating parities for data recovery. In particular, the present disclosure relates to a cache oblivious algorithm for generating parities and repairing data erasures using a butterfly code encoding algorithm.
Various encoding algorithms are available for encoding and decoding large amounts of data. Previous encoding techniques have shown that a surprisingly large amount of time may be spent encoding/decoding the code words. Additionally, the time spent by the CPU increases as the number of drives storing the code words increases. Software implementations typically use the host CPU's cache in a sub-optimal manner while constructing the parities and repairing from erasure of any one drive storing data. Thus, there is a need for a single algorithm to access the cache optimally, such that the algorithm optimizes the software performance of butterfly encoding/decoding. Such algorithms may also be reused to repair erasure of data from one or more drives.